A Boolean function $f:\{0,1\}^n \mapsto \{0,1\}$ is said to be $\eps$-farfrom monotone if $f$ needs to be modified in at least $\eps$-fraction of thepoints to make it monotone. We design a randomized tester that is given oracleaccess to $f$ and an input parameter $\eps>0$, and has the following guarantee:It outputs {\sf Yes} if the function is monotonically non-decreasing, andoutputs {\sf No} with probability $>2/3$, if the function is $\eps$-far frommonotone. This non-adaptive, one-sided tester makes$O(n^{7/8}\eps^{-3/2}\ln(1/\eps))$ queries to the oracle.
展开▼
